package a;

import java.util.*;


//拿不拿
public class 每样一个凑和_拿不拿{

    static int[] p;
    public static void main(String[] args) {
        p = new int[]{3,5,3,3,5,5,3,5,3,2,3,6};
        int tS=8,ci=0;
//        System.out.println(ljs(tS, ci));
//        System.out.println(minGS(tS, ci));

//        jutinafa(tS, ci); //上面有res干扰，我先注释掉了
        //去重 先排序+子集、从0起+fi (全排列是vis无关)
        Arrays.sort(p);
        asx(0,8);
        System.out.println(res);
    }
    private static void asx(int ci,int sum) {
        if(ci==p.length){
            //每个起点只向前走,走到头的List集合 res.add(new ArrayList<>(tmp));
            return;
        }

        for (int i = ci; i < p.length; i++) {
            tmp.add(p[i]);
            if(sum-p[i]==0) res.add(new ArrayList<>(tmp));
            //
            asx(i+1,sum-p[i]);
            //
            tmp.remove(tmp.size()-1);
        }
    }

    //最少币个
    private static int minGS(int tS, int ci) {
        if(ci==p.length){
            if(tS==0)return 0;//最少币数r0
            return 9999;
        }
        return Math.min(
                minGS(tS-p[ci],ci+1) +1,
                minGS(tS,ci+1)
        );
    }



    //具体拿法List
    static Set<List<Integer>> res = new HashSet<>();
    static List<Integer> tmp = new ArrayList<>();
    static void jutinafa(int tS, int ci) {
        //不用n个用完，很可能中间就够了
        if(tS==0){
            res.add(new ArrayList<>(tmp));
            return;
        }
        if(ci==p.length){
            if(tS==0)res.add(new ArrayList<>(tmp));
            return;
        }

        //na                                                                            //buna
        tmp.add(p[ci]);jutinafa(tS-p[ci],ci+1);tmp.remove(tmp.size()-1);   jutinafa(tS,ci+1);
    }
    //具体拿法个数
    static int ljs(int tS, int ci) {
        if(ci==p.length){
            if(tS==0)return 1;//路径可达static：1
            return 0;
        }
        return ljs(tS-p[ci],ci+1) + ljs(tS,ci+1);
    }


}
